package com.vinjune.algorithm.algorithms;


/**
*@author 作者：zhangwenjun
*@version 创建时间：2015年12月9日 下午5:18:41
* 多源最短路径
*/

public class Floyd {
	
private static int MAX = Integer.MAX_VALUE; //表示不可达
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 7;
		int[][] cost = new int[][]{{0,20,50,30,MAX,MAX,MAX},
							      {MAX,0,25,MAX,MAX,70,MAX},
							      {MAX,MAX,0,40,25,50,MAX},
							      {MAX,MAX,MAX,0,55,MAX,MAX},
							      {MAX,MAX,MAX,MAX,0,10,70},
							      {MAX,MAX,MAX,MAX,MAX,0,50},
							      {MAX,MAX,MAX,MAX,MAX,MAX,0}};
		floyd(n, cost);
	}

	/**
	 * 弗洛伊德求解过程
	 * @param n
	 * @param cost
	 */
	public static void floyd(int n, int[][] cost) {
		int[][] path = new int[n][n]; //path用来存放最后的结果
		//init
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++)
				path[i][j] = cost[i][j];
		}
		//floyd O(n^3)
		for(int s=0;s<n;s++)
			for(int t=0;t<n;t++)
				for(int k=0;k<n;k++) {
					if(path[s][k]!=MAX && path[k][t]!=MAX) { //如果有MAX最大值，那么相加后，会变成负数，导致结果出错
						if(path[s][k]+path[k][t] < path[s][t])
							path[s][t] = path[s][k]+path[k][t];
					}
				}
		//print
		for(int m=0;m<n;m++) {
			for(int l=0;l<n;l++)
				System.out.print(path[m][l] + " ");
			System.out.println();
		}
	}

}


